﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution34
    {
        public int[] SearchRange(int[] nums, int target)
        {
            int[] res = new int[2];

            //两次二分查找
            //先找最左边的
            int lower = BinarySearchL(nums, target);
            //再找最右边的
            int higher = BinarySearchR(nums, target);

            Console.WriteLine(lower);
            Console.WriteLine(higher);
            if (lower <= higher && higher < nums.Length && nums[lower] == target && nums[higher] == target)
            {
                res[0] = lower;
                res[1] = higher;
            }
            else
            {
                res[0] = -1;
                res[1] = -1;
            }
            return res;
        }

        private int BinarySearchL(int[] nums, int target)
        {
            int res = 0;

            int left = 0, right = nums.Length - 1;

            while (left <= right)
            {
                int mid = (left + right) / 2;

                if (nums[mid] < target)//去右边
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                    res = mid;
                }
            }

            return res;
        }

        private int BinarySearchR(int[] nums, int target)
        {
            int res = 0;

            int left = 0, right = nums.Length - 1;

            while (left <= right)
            {
                int mid = (left + right) / 2;

                if (nums[mid] <= target)//去右边
                {
                    left = mid + 1;
                    res = mid;
                }
                else
                {
                    right = mid - 1;
                }
            }

            return res;
        }
    }

    internal class Program34
    {
        private static void Main34(string[] args)
        {
            // int[] nums = [5, 7, 7, 8, 8, 10];
            int[] nums = [];
            int target = 8;
            Solution34 solution = new Solution34();
            int[] res = solution.SearchRange(nums, target);
            Console.WriteLine(res[0] + "," + res[1]);
        }
    }
}